package dfsMaze;

public class Main {
	// 方向数组：上、下、左、右
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};
    private static final int SIZE = 10;
    /**
     * 判断是否存在从起点 'S' 到终点 'E' 的路径
     * @param maze 10x10 的迷宫字符数组
     * @return 如果存在路径返回 true，否则返回 false
     */
    public static boolean canEscapeMaze(char[][] maze) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return false;
        }
        // 用于标记已经访问过的位置，避免重复访问和死循环
        boolean[][] visited = new boolean[SIZE][SIZE];
        // 寻找起点 'S' 的位置
        int startX = -1, startY = -1;
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (maze[i][j] == 'S') {
                    startX = i;
                    startY = j;
                    break;
                }
            }
            if (startX != -1) break;
        }
        // 从起点开始进行 DFS 搜索
        return dfs(maze, startX, startY, visited);
    }
    /**
     * 深度优先搜索
     * @param maze 迷宫
     * @param x 当前横坐标
     * @param y 当前纵坐标
     * @param visited 访问标记数组
     * @return 从当前位置能否到达终点
     */
    public static boolean dfs(char[][] maze, int x, int y, boolean[][] visited) {
        // 边界检查
        if (x < 0 || x >= SIZE || y < 0 || y >= SIZE) {
            return false;
        }
        // 如果已经访问过，避免重复搜索
        if (visited[x][y]) {
            return false;
        }
        // 如果是障碍物，不能通行
        if (maze[x][y] == '#') {
            return false;
        }
        // 如果到达终点，成功！
        if (maze[x][y] == 'E') {
            return true;
        }
        // 标记当前位置为已访问
        visited[x][y] = true;
        // 向四个方向进行递归搜索
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            
            if (dfs(maze, newX, newY, visited)) {
                return true; // 只要有一个方向能到达终点，就返回 true
            }
        }
        // 所有方向都走不通
        return false;
    }
	public static void main(String[] args) {
		// 示例 1：存在路径
        char[][] maze1 = {
            {'S', '.', '.', '#', '.', '.', '.', '.', '.', '.'},
            {'.', '#', '.', '#', '.', '#', '#', '#', '#', '.'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '#', '.'},
            {'.', '#', '#', '#', '#', '#', '#', '.', '#', '.'},
            {'.', '.', '.', '.', '.', '.', '#', '.', '#', '.'},
            {'#', '#', '#', '#', '#', '.', '#', '.', '#', '.'},
            {'.', '.', '.', '.', '#', '.', '#', '.', '#', '.'},
            {'.', '#', '#', '.', '#', '.', '#', '.', '#', '.'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '#', '#', '#', '#', '#', '#', '#', '#', 'E'}
        };
        System.out.println("迷宫1 是否有路径: " + canEscapeMaze(maze1)); // 输出: true
        // 示例 2：无路径
        char[][] maze2 = {
            {'S', '#', '#', '#', '#', '#', '#', '#', '#', 'E'},
            {'.', '#', '.', '.', '.', '.', '#', '.', '.', '.'},
            {'.', '#', '.', '#', '#', '#', '#', '#', '#', '.'},
            {'.', '#', '.', '#', '.', '.', '.', '.', '#', '.'},
            {'.', '#', '.', '#', '.', '#', '#', '.', '#', '.'},
            {'.', '#', '.', '#', '.', '#', '#', '.', '#', '.'},
            {'.', '#', '.', '#', '.', '.', '.', '.', '#', '.'},
            {'.', '#', '.', '#', '#', '#', '#', '#', '#', '.'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '#', '.'},
            {'.', '.', '.', '.', '#', '#', '#', '.', '#', '.'}
        };
        System.out.println("迷宫2 是否有路径: " + canEscapeMaze(maze2)); // 输出: false
	}
}
